Cache is a storage area that keeps frequently accessed data or program instructions readily available so that data or program instructions (both referred to hereafter, as "data") used by a computer do not have to be repeatedly retrieved from a secondary storage area. In one typical scheme, cache is a form of random access memory (RAM) which can be directly and quickly accessed by the computer's processor. In contrast to cache, a computer also includes one or more secondary storage areas, typically disk devices, which can only be accessed through an input/output (I/O) device, thereby providing much slower access time than the cache. Ideally, a computer would run entirely from data stored in RAM-type cache. However, RAM is very expensive relative to disk memory. Thus, a small amount of cache is provided in the computer (relative to memory capacity of the disks) to improve overall performance of the computer.
FIG. 1 shows a prior art computer system 10 which uses cache. The cache in FIG. 1 is "software cache" or "disk cache" which is designed to store data and program instructions which are frequently accessed from a disk drive or tape drive. The system 10 is shown with an application software program 12 running and issuing I/O requests to a cache manager 14. The cache manager 14 retains data recently accessed from one or more physical disks, collectively referred to as disk 16, which data is stored in cache 18 within the cache manager 14. If the program 12 requests data which exists in the cache 18, the data is retrieved directly from the cache 18 and no read request for the data is sent to the disk 16. However, if the requested data is not in the cache 18, the cache manager 14 issues an I/O read request to the disk 16, resulting in a seek and transfer of data from the disk 16 into the cache 18. Then, the cache manager 14 copies the data (now stored in the cache 18 for potential subsequent use) into the memory of the application program 12 (not shown) for immediate use.
In one conventional system 10, the cache 18 is divided into "pages" and the data in the cache 18 includes pages of one or more application program instructions and/or pages of data used by the one or more programs. When the application program 12 requests a page, and the page is not in the cache 18, a "page fault" occurs. Upon the occurrence of a "page fault," the cache manager 14 transmits a disk read request to the disk 16 to retrieve the page. The retrieved page is forwarded to the application program 12 and is cached for potential subsequent use.
The "cache hit rate" is a measure of the percentage of times that the requested data is available in the cache 18, and, thus, does not need to be retrieved from the disk 16. Disk drive life and program execution speed will improve as the cache hit rate increases, since read requests cause physical wear and since data access time from cache is typically significantly faster than data access time from a disk. Many schemes have been developed to optimize the disk cache process so as to minimize the number of seek and read requests for data stored on the disk 16. Some schemes affect how the cache 18 is "populated" or "primed" with data. Other schemes are used to decide which data should be purged from the cache 18 as the space in the cache 18 becomes filled. Still other schemes are used to decide how to share valuable computer RAM between virtual memory and disk cache. U.S. Pat. No. 5,581,736 (Smith), which is incorporated by reference in its entirety herein, is one example of the latter scheme.
One conventional scheme to improve the cache hit rate is to pre-read additional, unrequested data whenever a disk read request occurs. More specifically, this scheme reads the requested data from the disk, as well as a small amount of additional data on the disk which follows the requested data. This scheme is based on the fact that data which is physically stored on the disk after the requested data is oftentimes likely to be needed shortly after the requested data is needed. The amount of additional, unrequested data that is read from the disk is called the "read ahead size." One conventional disk caching subsystem provided in Microsoft Windows.RTM. has a small, fixed read-ahead size which can be preset by the user up to a maximum value of 64 kilobytes (64 K). For example, if the read-ahead size is 64K and 10K of data must be retrieved from the disk because it is immediately needed and is not present in the cache, then 74K of data is retrieved and cached. The 74K of data consists of the requested 10K, plus the subsequent 64K of data on the disk. Likewise, if the read-ahead size is 64K and 100K of data must be retrieved from the disk because the 100K of data is immediately needed and is not present in the cache, then 164K of data is retrieved and cached. Some disadvantages of this scheme are as follows:
(1) The maximum read-ahead size is very small, thereby limiting the amount of additional data that is pre-read into the cache for potential subsequent use.
(2) The read-ahead size is fixed and thus cannot dynamically change based upon system performance.
(3) The additional read data (i.e., read-ahead data) is always data which follows the requested data. In some instances, a program is likely to need data which precedes the requested data. In the conventional scheme, a separate disk read must be performed to obtain the preceding data unless the preceding data was coincidentally captured as part of the read-ahead data associated with a different prior disk read operation.
Despite the many schemes for improving and optimizing disk cache performance, there is still a need to further improve and optimize performance, and thus further reduce the number of disk read requests. The present invention fulfills this need.